\chapter{现代密码学}

\section{哈希算法}

\subsection{哈希函数（Hash Function）}

哈希函数可以把任意长度的数据转换为一个为固定长度的结果，其中要计算的数据称为源数据，计算后的结果数据称为哈希值或摘要（digest）。\\

不同的哈希函数对应不同的哈希算法，常见的有MD5（Message Digest Algorithm 5）、SHA1（Secure Hash Algorithm）、SHA224、SHA256、SHA384、SHA512等。\\

哈希算法的特点包括：

\begin{itemize}
    \item 对相同的源数据采用相同的哈希算法，得到的哈希值一定相同。
    \item 无论源数据有多长，哈希值的长度都是固定的。
    \item 算法不可逆，即无法从哈希值反向推导出源数据。
\end{itemize}

\vspace{0.5cm}

\subsection{哈希冲突（Hash Collision）}

对于不同的源数据使用同样的哈希算法，有可能会产生相同的哈希值，这种现象称为哈希冲突。\\

一般来说，源数据的长度越长，哈希冲突的概率越小，但耗费的计算时长也越长。例如MD5算法，冲突率非常小，约等于$ 1.47 \times 10^{-29} $，几乎可以忽略不计。\\

\mybox{哈希函数}

\begin{lstlisting}[language=Python]
import hashlib


def md5(plaintext):
    h = hashlib.md5()
    h.update(plaintext.encode())
    return h.hexdigest()


def sha256(plaintext):
    h = hashlib.sha256()
    h.update(plaintext.encode())
    return h.hexdigest()


def sha512(plaintext):
    h = hashlib.sha512()
    h.update(plaintext.encode())
    return h.hexdigest()


def main():
    plaintext = "Hello World"

    print("MD5: ", md5(plaintext))
    print("SHA256: ", sha256(plaintext))
    print("SHA512: ", sha512(plaintext))


if __name__ == "__main__":
    main()
\end{lstlisting}

\newpage

\section{RSA}

\subsection{RSA}

RSA是一种非对称加密（asymmetric cryptography）算法，在1977年由Ron Rivest、Adi ShamirLeonard Adleman一起提出，RSA就是他们三人姓氏的首字母。\\

所谓非对称加密，是指在网络通信中双方各有一对密钥，其中公钥（public key）被公开给外界，用于加密；私钥（private key）只有自己知道，用于解密。\\

例如Alice的一组密钥为$ (P_A, S_A) $，Bob的一组密钥为$ (P_B, S_B) $。对一段消息$ M $加密和解密的操作是互逆的：

\vspace{-1cm}

\begin{align*}
    M & = S_A(P_A(M)) \\
    M & = P_A(S_A(M))
\end{align*}

如果Bob想要给Alice发送消息，Bob首先使用Alice的公钥$ P_A $对消息$ M $进行加密得到密文$ C $：

\vspace{-1cm}

\begin{align*}
    C = P_A(M)
\end{align*}

Bob将密文$ C $发送给Alice，Alice使用自己的私钥$ S_A $对密文$ C $进行解密得到原文$ M $：

\vspace{-1cm}

\begin{align*}
    S_A(C) = S_A(P_A(M)) = M
\end{align*}

\vspace{0.5cm}

\subsection{公钥/私钥生成}

RSA的安全性依赖于大整数的质因数分解，也就是对于两个大素数$ p $和$ q $而言，计算它们的乘积$ pq $很容易，但是从积$ pq $分解出$ p $和$ q $是个公认的数学难题。\\

RSA公钥和私钥生成的过程如下：

\begin{enumerate}
    \item 随机选择两个大素数（超过100位），为了简化说明，这里采用较小的素数$ p = 41 $、$ q = 59 $

    \item 计算$ p $和$ q $的乘积$ n = pq = 2419 $

    \item 计算$ p - 1 $与$ q - 1 $的乘积$ \phi(n) = (p-1)(q-1) = 40 * 58 = 2320 $

    \item 选择一个小奇数$ e $，使得$ gcd(e, \phi(n)) = 1$，例如$ e = 3 $

    \item 计算$ d $，使得$ d * e \equiv 1\ (\text{mod}\ \phi(n)) $。当$ d = 1547 $时，$ 1547 * 3\ \text{mod}\ 2320 = 1 $

    \item 公钥$ P = (e, n) = (3, 2419) $

    \item 私钥$ S = (d, n) = (1547, 2419) $

    \item 对消息$ M $加密的过程为$ P(M) = M^e\ (\text{mod}\ n) = M^3\ (\text{mod}\ 2419) $

    \item 对消息$ M $解密的过程为$ S(M) = M^d\ (\text{mod}\ n) = M^{1547}\ (\text{mod}\ 2419) $
\end{enumerate}

\vspace{0.5cm}

\subsection{加密}

假设Alice的公钥为$ (9, 2419) $，想要将消息“PACE”发送给Bob。\\

首先将消息中的英文字母转换为对应的编码：

\begin{itemize}
    \item PA = 1500
    \item CE = 0204
\end{itemize}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|}
            \hline
            \textbf{Letter} & \textbf{Code} & \textbf{Letter} & \textbf{Code} \\
            \hline
            A               & 00            & B               & 01            \\
            \hline
            C               & 02            & D               & 03            \\
            \hline
            E               & 04            & F               & 05            \\
            \hline
            G               & 06            & H               & 07            \\
            \hline
            I               & 08            & J               & 09            \\
            \hline
            K               & 10            & L               & 11            \\
            \hline
            M               & 12            & N               & 13            \\
            \hline
            O               & 14            & P               & 15            \\
            \hline
            Q               & 16            & R               & 17            \\
            \hline
            S               & 18            & T               & 19            \\
            \hline
            U               & 20            & V               & 21            \\
            \hline
            W               & 22            & X               & 23            \\
            \hline
            Y               & 24            & Z               & 25            \\
            \hline
        \end{tabular}
    }
\end{table}

分别对PA和CE进行加密：

\begin{itemize}
    \item $ P(1500) = 1500^9\ (\text{mod}\ 2419) = 1655 $
    \item $ P(0204) = 204^9\ (\text{mod}\ 2419) = 1639 $
\end{itemize}

最终形成的密文为1655 1639。

\newpage

\section{DES}

\subsection{DES（Data Encryption Standard）}

DES是一种分组密码，它将数据分成多个64位的块，每个块独立加密。因此，DES将64位的明文作为输入，输出64位的密文。\\

DES首先需要对原始数据进行一次初始置换（IP, Initial Permutation），接着进行16轮迭代运算，对数据重新排列和置换，最后再对数据进行一次最终置换（FP, Final Permutation），得到最终的密文。\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[node distance=2cm]
        \node (start) [startend] {Start};
        \node (IP) [process, below of=start] {IP};
        \node (round1) [process, below of=IP] {Round 1};
        \node (key1) [process, right of=round1, xshift=3cm] {Key 1};
        \node (round2) [process, below of=round1] {Round 2};
        \node (key2) [process, right of=round2, xshift=3cm] {Key 2};
        \node (roundx) [process, below of=round2] {Round $ x $};
        \node (keyx) [process, right of=roundx, xshift=3cm] {Key $ x $};
        \node (round16) [process, below of=roundx] {Round 16};
        \node (key16) [process, right of=round16, xshift=3cm] {Key 16};
        \node (FP) [process, below of=round16] {FP};
        \node (end) [startend, below of=FP] {End};

        \draw [arrow] (start) -- (IP);
        \draw [arrow] (IP) -- (round1);
        \draw [arrow] (key1) -- (round1);
        \draw [arrow] (key2) -- (round2);
        \draw [arrow] (round1) -- (round2);
        \draw [arrow] (round2) -- (roundx);
        \draw [arrow] (keyx) -- (roundx);
        \draw [arrow] (roundx) -- (round16);
        \draw [arrow] (key16) -- (round16);
        \draw [arrow] (round16) -- (FP);
        \draw [arrow] (FP) -- (end);
    \end{tikzpicture}
    \caption{DES}
\end{figure}

\vspace{0.5cm}

\subsection{密钥生成}

由于在DES的16轮迭代加密的过程中，每一轮都需要使用一个不同的密钥。因此，在DES开始加密之前，需要先根据原始的密钥，生成16个不同的密钥。\\

原始的密钥的长度为64位，其中第8、16、24、32、40、48、56、64位为奇偶校验位。因此，忽略这8位奇偶校验位，然后对剩余的56位进行重新排列，排列的顺序参照PC-1表。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|}
            \hline
            57 & 49 & 41 & 33 & 25 & 17 & 9  \\
            \hline
            1  & 58 & 50 & 42 & 34 & 26 & 18 \\
            \hline
            10 & 2  & 59 & 51 & 43 & 35 & 27 \\
            \hline
            19 & 11 & 3  & 60 & 52 & 44 & 36 \\
            \hline
            63 & 55 & 47 & 39 & 31 & 23 & 15 \\
            \hline
            7  & 62 & 54 & 46 & 38 & 30 & 22 \\
            \hline
            14 & 6  & 61 & 53 & 45 & 37 & 29 \\
            \hline
            21 & 13 & 5  & 28 & 20 & 12 & 4  \\
            \hline
        \end{tabular}
    }
    \caption{PC-1}
\end{table}

其中PC-1的每个数字代表依次排列的位置，例如57代表将原始密钥第57位放到第1位，40代表将原始密钥第40位放到第2位，依次类推。由于PC-1表中只包含56个位置，在进行重新选择排列的过程中，即可忽略掉8位奇偶校验位。\\

例如原始密钥为：

\begin{verbatim}
    00010011 00110100
    01010111 01111001
    10011011 10111100
    11011111 11110001
\end{verbatim}

重新选择排列后得到一个56位的密钥：

\begin{verbatim}
    1111000 0110011
    0010101 0101111
    0101010 1011001
    1001111 0001111
\end{verbatim}

接着将56位的密钥分为两部分，分别为左28位和右28位，分别对它们进行16次循环左移，循环左移的次数参照移位表。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
            \textbf{第$ i $轮}    & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\
            \hline
            \textbf{循环左移位数} & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 2  & 2  & 2  & 2  & 2  & 2  & 1  \\
            \hline
        \end{tabular}
    }
    \caption{移位表}
\end{table}

在每一轮循环左移后，将左右两部分重新，拼接成一个56位的密钥，然后对这个56位的密钥进行重新选择排列，最终生成每一轮的48位密钥，排列的顺序参照PC-2表。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|c|}
            \hline
            14 & 17 & 11 & 24 & 1  & 5  \\
            \hline
            3  & 28 & 15 & 6  & 21 & 10 \\
            \hline
            23 & 19 & 12 & 4  & 26 & 8  \\
            \hline
            16 & 7  & 27 & 20 & 13 & 2  \\
            \hline
            41 & 52 & 31 & 37 & 47 & 55 \\
            \hline
            30 & 40 & 51 & 45 & 33 & 48 \\
            \hline
            44 & 49 & 39 & 56 & 34 & 53 \\
            \hline
            46 & 42 & 50 & 36 & 29 & 32 \\
            \hline
        \end{tabular}
    }
    \caption{PC-2}
\end{table}

\vspace{0.5cm}

\subsection{初始置换IP}

在生成16个密钥后，就可以对明文进行加密了。第一步需要先对明文进行IP置换，IP置换的顺序参照IP表。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|}
            \hline
            58 & 50 & 42 & 34 & 26 & 18 & 10 & 2 \\
            \hline
            60 & 52 & 44 & 36 & 28 & 20 & 12 & 4 \\
            \hline
            62 & 54 & 46 & 38 & 30 & 22 & 14 & 6 \\
            \hline
            64 & 56 & 48 & 40 & 32 & 24 & 16 & 8 \\
            \hline
            57 & 49 & 41 & 33 & 25 & 17 & 9  & 1 \\
            \hline
            59 & 51 & 43 & 35 & 27 & 19 & 11 & 3 \\
            \hline
            61 & 53 & 45 & 37 & 29 & 21 & 13 & 5 \\
            \hline
            63 & 55 & 47 & 39 & 31 & 23 & 15 & 7 \\
            \hline
        \end{tabular}
    }
    \caption{IP}
\end{table}

\vspace{0.5cm}

\subsection{16轮迭代}

将置换后的64位明文分为左32位和右32位，然后进行16轮迭代加密，每一轮的处理过程如下：\\

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \draw (0,10) rectangle (3,10.75) node[xshift=-1.5cm, yshift=-0.5cm] {$ L_0 $};
        \draw (7,10) rectangle (10,10.75) node[xshift=-1.5cm, yshift=-0.5cm] {$ R_0 $};

        \node[draw, trapezium] (E) at (8.5,8.5) {E扩展};
        \node [XORgate] at (8.5,7) (XOR1) {\large +};
        \node[draw, trapezium, rotate=180] (S) at (8.5,5.5) {\textcolor{white}{S盒}};
        \node at (8.5,5.5) {S盒};
        \node[draw, rectangle] (P) at (8.5,4) {P盒};
        \node [XORgate] at (8.5,2.25) (XOR2) {\large +};

        \draw (0,0) rectangle (3,0.75) node[xshift=-1.5cm, yshift=-0.5cm] {$ L_1 $};
        \draw (7,0) rectangle (10,0.75) node[xshift=-1.5cm, yshift=-0.5cm] {$ R_1 $};

        \draw (11,7) node[right] {$ key_i $} -- (XOR1);
        \node at (10,6.7) {48};

        \draw (1.5,10) node[right, yshift=-0.5cm] {32} -- (1.5,4) -- (XOR2);
        \draw (8.5,10) node[right, yshift=-0.5cm] {32} -- (E);
        \draw (8.5,9.5) -- (6,9) -- (1.5,0.75) node[above, yshift=0.3cm] {32};
        \draw (E) -- (XOR1) node[left, xshift=-0.2cm, yshift=0.7cm] {48};
        \draw (XOR1) -- (S) node[left, xshift=-0.2cm, yshift=0.7cm] {48};
        \draw (S) -- (P) node[left, xshift=-0.2cm, yshift=0.7cm] {32};
        \draw (P) -- (XOR2) node[left, xshift=-0.2cm, yshift=0.8cm] {32};
        \draw (XOR2) -- (8.5,0.75) node[left, xshift=-0.2cm, yshift=0.5cm] {32};
    \end{tikzpicture}
    \caption{16轮迭代}
\end{figure}

\vspace{0.5cm}

\subsection{E扩展（Expansion Permutation）}

E扩展将32位的右半部分扩展为48位，扩展的顺序参照E表。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|}
            \hline
            32 & 1  & 2  & 3  & 4  & 5  & 4  & 5  \\
            \hline
            6  & 7  & 8  & 9  & 8  & 9  & 10 & 11 \\
            \hline
            12 & 13 & 12 & 13 & 14 & 15 & 16 & 17 \\
            \hline
            16 & 17 & 18 & 19 & 20 & 21 & 20 & 21 \\
            \hline
            22 & 23 & 24 & 25 & 24 & 25 & 26 & 27 \\
            \hline
            28 & 29 & 28 & 29 & 30 & 31 & 32 & 1  \\
            \hline
        \end{tabular}
    }
    \caption{E}
\end{table}

E扩展的规则其实是将原来的32位以4位一组划分，然后将每一组的最后一位复制到后一组的前面，将每一组的第一位复制到前一组的后面，（其中第一组的前一组为最后一组，最后一组的下一组为第一组）。\\

这样就可以将4位一组扩展为6位一组，最后按顺序合并，即可得到48位的结果。\\

最后将扩展完的48位与之前生成的该轮密钥进行异或运算，得到48位的结果。\\

\subsection{S盒（S-Box Substitution）}

S盒用于将48位的数据压缩为32位。首先将48位的数据分为8组，每组6位，每一组都会根据对应的S盒（共8个，$ S_1 \sim S_8 $）进行压缩。因此，每个S盒都需要将6位输入压缩为4位输出。\\

每个S盒都由4行16列组成：\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 14         & 4          & 13         & 1          & 2          & 15         & 11         & 8          & 3          & 10         & 6           & 12          & 5           & 9           & 0           & 7           \\
            \hline
            \textbf{1} & 0          & 15         & 7          & 4          & 14         & 2          & 13         & 1          & 10         & 6          & 12          & 11          & 9           & 5           & 3           & 8           \\
            \hline
            \textbf{2} & 4          & 1          & 14         & 8          & 13         & 6          & 2          & 11         & 15         & 12         & 9           & 7           & 3           & 10          & 5           & 0           \\
            \hline
            \textbf{3} & 15         & 12         & 8          & 2          & 4          & 9          & 1          & 7          & 5          & 11         & 3           & 14          & 10          & 0           & 6           & 13          \\
            \hline
        \end{tabular}
    }
    \caption{$ S_1 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 15         & 1          & 8          & 14         & 6          & 11         & 3          & 4          & 9          & 7          & 2           & 13          & 12          & 0           & 5           & 10          \\
            \hline
            \textbf{1} & 3          & 13         & 4          & 7          & 15         & 2          & 8          & 14         & 12         & 0          & 1           & 10          & 6           & 9           & 11          & 5           \\
            \hline
            \textbf{2} & 0          & 14         & 7          & 11         & 10         & 4          & 13         & 1          & 5          & 8          & 12          & 6           & 9           & 3           & 2           & 15          \\
            \hline
            \textbf{3} & 13         & 8          & 10         & 1          & 3          & 15         & 4          & 2          & 11         & 6          & 7           & 12          & 0           & 5           & 14          & 9           \\
            \hline
        \end{tabular}
    }
    \caption{$ S_2 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 10         & 0          & 9          & 14         & 6          & 3          & 15         & 5          & 1          & 13         & 12          & 7           & 11          & 4           & 2           & 8           \\
            \hline
            \textbf{1} & 13         & 7          & 0          & 9          & 3          & 4          & 6          & 10         & 2          & 8          & 5           & 14          & 12          & 11          & 15          & 1           \\
            \hline
            \textbf{2} & 13         & 6          & 4          & 9          & 8          & 15         & 3          & 0          & 11         & 1          & 2           & 12          & 5           & 10          & 14          & 7           \\
            \hline
            \textbf{3} & 1          & 10         & 13         & 0          & 6          & 9          & 8          & 7          & 4          & 15         & 14          & 3           & 11          & 5           & 2           & 12          \\
            \hline
        \end{tabular}
    }
    \caption{$ S_3 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 7          & 13         & 14         & 3          & 0          & 6          & 9          & 10         & 1          & 2          & 8           & 5           & 11          & 12          & 4           & 15          \\
            \hline
            \textbf{1} & 13         & 8          & 11         & 5          & 6          & 15         & 0          & 3          & 4          & 7          & 2           & 12          & 1           & 10          & 14          & 9           \\
            \hline
            \textbf{2} & 10         & 6          & 9          & 0          & 12         & 11         & 7          & 13         & 15         & 1          & 3           & 14          & 5           & 2           & 8           & 4           \\
            \hline
            \textbf{3} & 3          & 15         & 0          & 6          & 10         & 1          & 13         & 8          & 9          & 4          & 5           & 11          & 12          & 7           & 2           & 14          \\
            \hline
        \end{tabular}
    }
    \caption{$ S_4 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 2          & 12         & 4          & 1          & 7          & 10         & 11         & 6          & 8          & 5          & 3           & 15          & 13          & 0           & 14          & 9           \\
            \hline
            \textbf{1} & 14         & 11         & 2          & 12         & 4          & 7          & 13         & 1          & 5          & 0          & 15          & 10          & 3           & 9           & 8           & 6           \\
            \hline
            \textbf{2} & 4          & 2          & 1          & 11         & 10         & 13         & 7          & 8          & 15         & 9          & 12          & 5           & 6           & 3           & 0           & 14          \\
            \hline
            \textbf{3} & 11         & 8          & 12         & 7          & 1          & 14         & 2          & 13         & 6          & 15         & 0           & 9           & 10          & 4           & 5           & 3           \\
            \hline
        \end{tabular}
    }
    \caption{$ S_5 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 12         & 1          & 10         & 15         & 9          & 2          & 6          & 8          & 0          & 13         & 3           & 4           & 14          & 7           & 5           & 11          \\
            \hline
            \textbf{1} & 10         & 15         & 4          & 2          & 7          & 12         & 9          & 5          & 6          & 1          & 13          & 14          & 0           & 11          & 3           & 8           \\
            \hline
            \textbf{2} & 9          & 14         & 15         & 5          & 2          & 8          & 12         & 3          & 7          & 0          & 4           & 10          & 1           & 13          & 11          & 6           \\
            \hline
            \textbf{3} & 4          & 3          & 2          & 12         & 9          & 5          & 15         & 10         & 11         & 14         & 1           & 7           & 6           & 0           & 8           & 13          \\
            \hline
        \end{tabular}
    }
    \caption{$ S_6 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 4          & 11         & 2          & 14         & 15         & 0          & 8          & 13         & 3          & 12         & 9           & 7           & 5           & 10          & 6           & 1           \\
            \hline
            \textbf{1} & 13         & 0          & 11         & 7          & 4          & 9          & 1          & 10         & 14         & 3          & 5           & 12          & 2           & 15          & 8           & 6           \\
            \hline
            \textbf{2} & 1          & 4          & 11         & 13         & 12         & 3          & 7          & 14         & 10         & 15         & 6           & 8           & 0           & 5           & 9           & 2           \\
            \hline
            \textbf{3} & 6          & 11         & 13         & 8          & 1          & 4          & 10         & 7          & 9          & 5          & 0           & 15          & 14          & 2           & 3           & 12          \\
            \hline
        \end{tabular}
    }
    \caption{$ S_7 $}
\end{table}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{2mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} \\
            \hline
            \textbf{0} & 13         & 2          & 8          & 4          & 6          & 15         & 11         & 1          & 10         & 9          & 3           & 14          & 5           & 0           & 12          & 7           \\
            \hline
            \textbf{1} & 1          & 15         & 13         & 8          & 10         & 3          & 7          & 4          & 12         & 5          & 6           & 11          & 0           & 14          & 9           & 2           \\
            \hline
            \textbf{2} & 7          & 11         & 4          & 1          & 9          & 12         & 14         & 2          & 0          & 6          & 10          & 13          & 15          & 3           & 5           & 8           \\
            \hline
            \textbf{3} & 2          & 1          & 14         & 7          & 4          & 10         & 8          & 13         & 15         & 12         & 9           & 0           & 3           & 5           & 6           & 11          \\
            \hline
        \end{tabular}
    }
    \caption{$ S_8 $}
\end{table}

以$ S_1 $为例，如果该组的6位数据为101100，取首尾2位的十进制作为行、中间4位的十进制作为列，即行为$ 10_2 = 2_{10} $、列为$ 0110_2 = 6_{10} $。在$ S_1 $中找到第2行、第6列的数据2，转换为4位二进制0010，即为该组的压缩结果。\\

\subsection{P盒（P-Box Permutation）}

在经过8个S盒的压缩后，原本48位的数据会压缩为32位。将这32位数据按照P盒的规则重新排列，排列的顺序参照P-Box表。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|}
            \hline
            16 & 7  & 20 & 21 \\
            \hline
            29 & 12 & 28 & 17 \\
            \hline
            1  & 15 & 23 & 26 \\
            \hline
            5  & 18 & 31 & 10 \\
            \hline
            2  & 8  & 24 & 14 \\
            \hline
            32 & 27 & 3  & 9  \\
            \hline
            19 & 13 & 30 & 6  \\
            \hline
            22 & 11 & 4  & 25 \\
            \hline
        \end{tabular}
    }
    \caption{P盒}
\end{table}

最后将置换后的数据与左32位数据$ L_0 $进行异或运算，即可得到下一轮迭代的右32位数据$ R_1 $。\\

\subsection{最终置换FP}

在经过16轮迭代解密后，将最后一轮的左32位和右32位数据进行合并。将合并后的64位数据按照FP表的规则重新排列，排列的顺序参照FP表。\\

经过置换后的64位数据，即为最终DES加密后产生的密文。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|}
            \hline
            40 & 8 & 48 & 16 & 56 & 24 & 64 & 32 \\
            \hline
            39 & 7 & 47 & 15 & 55 & 23 & 63 & 31 \\
            \hline
            38 & 6 & 46 & 14 & 54 & 22 & 62 & 30 \\
            \hline
            37 & 5 & 45 & 13 & 53 & 21 & 61 & 29 \\
            \hline
            36 & 4 & 44 & 12 & 52 & 20 & 60 & 28 \\
            \hline
            35 & 3 & 43 & 11 & 51 & 19 & 59 & 27 \\
            \hline
            34 & 2 & 42 & 10 & 50 & 18 & 58 & 26 \\
            \hline
            33 & 1 & 41 & 9  & 49 & 17 & 57 & 25 \\
            \hline
        \end{tabular}
    }
    \caption{FP}
\end{table}

\newpage

\section{AES}

\subsection{AES（Advanced Encryption Standard）}

AES加密算法的提出是为了取代已经被证明不安全的DES算法。AES与DES一样属于分组加密，也就是将明文划分成若干个等长的明文块，分块进行加密。\\

AES规定明文的长度为128位，密钥的长度可以是128位、192位或256位。192位与256位的处理方式与128位是类似的，只不过在加密过程中迭代的次数不同而已。128位的密钥需要进行10轮迭代，192位需要12轮，256位需要14轮。\\

在AES加密算法中，将128位（16字节）明文以$ 4 \times 4 $的矩阵表示，数据按照从上到下、从左到右的顺序依次排列。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{5mm}{
        \begin{tabular}{|c|c|c|c|}
            \hline
            1 & 5 & 9  & 13 \\
            \hline
            2 & 6 & 10 & 14 \\
            \hline
            3 & 7 & 11 & 15 \\
            \hline
            4 & 8 & 12 & 16 \\
            \hline
        \end{tabular}
    }
\end{table}

AES加密的过程包括：

\begin{enumerate}
    \item 明文
    \item 初始变换
    \item 10轮迭代
          \begin{itemize}
              \item 字节代换
              \item 行移位
              \item 列混合（最后一轮迭代不执行）
              \item 轮密钥加
          \end{itemize}
    \item 密文
\end{enumerate}

\vspace{0.5cm}

\subsection{密钥扩展}

在对明文加密前，首先需要对密钥进行扩展，得到每一轮迭代的轮密钥。\\

首先创建一个能够存储原始密钥和10个轮密钥的矩阵，将原始密钥放在前4列。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{3mm}{
        \begin{tabular}{|c|c|c|c||c|c|c|c||c|c|c|c|}
            \hline
            2b & 28 & ab & 09 & \ \  & \ \  & \ \  & \ \  & \ \  & \ \  & \ \  & \ \ \\
            \hline
            7e & ae & f7 & cf & \ \  & \ \  & \ \  & \ \  & \ \  & \ \  & \ \  & \ \ \\
            \hline
            15 & d2 & 15 & 4f & \ \  & \ \  & \ \  & \ \  & \ \  & \ \  & \ \  & \ \ \\
            \hline
            16 & a6 & 88 & 3c & \ \  & \ \  &      & \ \  & \ \  & \ \  & \ \  & \ \ \\
            \hline
        \end{tabular}
    }
\end{table}

假设每一列用$ W_i $表示，那么$ W_0 $到$ W_3 $就是原始密钥。\\

后续每一列的扩展方式如下：

\begin{itemize}
    \item 如果$ i $不是4的倍数：$ W[i] = W[i-4] \oplus W[i-1] $
    \item 如果$ i $是4的倍数：$ W[i] = W[i-4] \oplus T(W[i-1]) $
\end{itemize}

对于$ i $是4的倍数的情况，首先需要使用函数$ T $对$ W[i-1] $进行变换，函数$ T $由三部分组成：

\begin{enumerate}
    \item 字循环
    \item 字节代换
    \item 轮常量异或
\end{enumerate}

\vspace{0.5cm}

\subsubsection{字循环}

字循环的作用是将$ W[i-1] $这一列数据进行循环左移1个字节。例如$ [09, cf, 4f, 3c] $将被转换为$ [cf, 4f, 3c, 09] $。\\

\subsubsection{字节代换}

字节代换会对字循环的结果使用S盒中的数据替换，替换规则为将每个字节分成行和列两部分，在S盒中使用对应行列的数据进行替换。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{1mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
            \hline
                       & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{a} & \textbf{b} & \textbf{c} & \textbf{d} & \textbf{e} & \textbf{f} \\
            \hline
            \textbf{0} & 63         & 7C         & 77         & 7B         & F2         & 6B         & 6F         & C5         & 30         & 01         & 67         & 2B         & FE         & D7         & AB         & 76         \\
            \hline
            \textbf{1} & CA         & 82         & C9         & 7D         & FA         & 59         & 47         & F0         & AD         & D4         & A2         & AF         & 9C         & A4         & 72         & C0         \\
            \hline
            \textbf{2} & B7         & FD         & 93         & 26         & 36         & 3F         & F7         & CC         & 34         & A5         & E5         & F1         & 71         & D8         & 31         & 15         \\
            \hline
            \textbf{3} & 04         & C7         & 23         & C3         & 18         & 96         & 05         & 9A         & 07         & 12         & 80         & E2         & EB         & 27         & B2         & 75         \\
            \hline
            \textbf{4} & 09         & 83         & 2C         & 1A         & 1B         & 6E         & 5A         & A0         & 52         & 3B         & D6         & B3         & 29         & E3         & 2F         & 84         \\
            \hline
            \textbf{5} & 53         & D1         & 00         & ED         & 20         & FC         & B1         & 5B         & 6A         & CB         & BE         & 39         & 4A         & 4C         & 58         & CF         \\
            \hline
            \textbf{6} & D0         & EF         & AA         & FB         & 43         & 4D         & 33         & 85         & 45         & F9         & 02         & 7F         & 50         & 3C         & 9F         & A8         \\
            \hline
            \textbf{7} & 51         & A3         & 40         & 8F         & 92         & 9D         & 38         & F5         & BC         & B6         & DA         & 21         & 10         & FF         & F3         & D2         \\
            \hline
            \textbf{8} & CD         & 0C         & 13         & EC         & 5F         & 97         & 44         & 17         & C4         & A7         & 7E         & 3D         & 64         & 5D         & 19         & 73         \\
            \hline
            \textbf{9} & 60         & 81         & 4F         & DC         & 22         & 2A         & 90         & 88         & 46         & EE         & B8         & 14         & DE         & 5E         & 0B         & DB         \\
            \hline
            \textbf{a} & E0         & 32         & 3A         & 0A         & 49         & 06         & 24         & 5C         & C2         & D3         & AC         & 62         & 91         & 95         & E4         & 79         \\
            \hline
            \textbf{b} & E7         & C8         & 37         & 6D         & 8D         & D5         & 4E         & A9         & 6C         & 56         & F4         & EA         & 65         & 7A         & AE         & 08         \\
            \hline
            \textbf{c} & BA         & 78         & 25         & 2E         & 1C         & A6         & B4         & C6         & E8         & DD         & 74         & 1F         & 4B         & BD         & 8B         & 8A         \\
            \hline
            \textbf{d} & 70         & 3E         & B5         & 66         & 48         & 03         & F6         & 0E         & 61         & 35         & 57         & B9         & 86         & C1         & 1D         & 9E         \\
            \hline
            \textbf{e} & E1         & F8         & 98         & 11         & 69         & D9         & 8E         & 94         & 9B         & 1E         & 87         & E9         & CE         & 55         & 28         & DF         \\
            \hline
            \textbf{f} & 8C         & A1         & 89         & 0D         & BF         & E6         & 42         & 68         & 41         & 99         & 2D         & 0F         & B0         & 54         & BB         & 16         \\
            \hline
        \end{tabular}
    }
    \caption{S盒}
\end{table}

因此，$ [cf, 4f, 3c, 09] $会被替换为$ [8a, 84, eb, 01] $。\\

\subsubsection{轮常量异或}

将经过S盒转换后的结果再与轮常量进行异或运算，每一轮的轮常量为轮常量表中的一列。\\

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{4mm}{
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
            \hline
            01 & 02 & 04 & 08 & 10 & 20 & 40 & 80 & 1b & 36 \\
            \hline
            00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
            \hline
            00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
            \hline
            00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
            \hline
        \end{tabular}
    }
    \caption{轮常量}
\end{table}

例如在第一轮迭代中，需要将S盒转换后的结果与第一列轮常量进行异或，即$ [8a, 84, eb, 01] \oplus [01, 00, 00, 00] = [88, 84, eb, 01] $。\\

完成这一步后，即完成了对$ T(W[i-1]) $的计算，再将其与$ W[i-4] $异或。

\vspace{-1cm}

\begin{align*}
    W[i] & = W[i-4] \oplus T(W[i-4])                  \\
         & = [2b, 7e, 15, 16] \oplus [88, 84, eb, 01] \\
         & = [a0, fa, fe, 17]
\end{align*}

根据密钥扩展的规则，最终可以产生每一轮所需的轮密钥。\\

\subsection{初始变换（Initial Round）}

在对明文加密的步骤中，首先将128位的明文转换成$ 4 \times 4 $的矩阵，并将其与原始密钥矩阵进行异或运算。

$$
    \begin{bmatrix}
        P_1 & P_5 & P_9  & P_13 \\
        P_2 & P_6 & P_10 & P_14 \\
        P_3 & P_7 & P_11 & P_15 \\
        P_4 & P_8 & P_12 & P_16
    \end{bmatrix}
    \oplus
    \begin{bmatrix}
        K_1 & K_5 & K_9  & K_13 \\
        K_2 & K_6 & K_10 & K_14 \\
        K_3 & K_7 & K_11 & K_15 \\
        K_4 & K_8 & K_12 & K_16
    \end{bmatrix}
$$

\vspace{0.5cm}

例如明文$ P $为：

$$
    \begin{bmatrix}
        32 & 88 & 31 & e0 \\
        43 & 5a & 31 & 37 \\
        f6 & 30 & 98 & 07 \\
        a8 & 8d & a2 & 34
    \end{bmatrix}
$$

\vspace{0.5cm}

原始密钥$ K $为：

$$
    \begin{bmatrix}
        2b & 28 & ab & 09 \\
        7e & ae & f7 & cf \\
        15 & d2 & 15 & 4f \\
        16 & a6 & 88 & 3c
    \end{bmatrix}
$$

\vspace{0.5cm}

则初始变换后的矩阵为：

$$
    \begin{bmatrix}
        19 & a0 & 9a & e9 \\
        3d & f4 & c6 & f8 \\
        e3 & e2 & 8d & 48 \\
        be & 2b & 2a & 08
    \end{bmatrix}
$$

\vspace{0.5cm}

\subsection{字节代换（SubBytes）}

字节代换需要将矩阵中的每个字节分为两部分，分别代表行和列，然后使用S盒中对应的行列位置上的值替换。例如19，则需要查找S盒的第1行、第9列，得到d4。\\

对上一步经过初始变换后的矩阵进行字节代换后的结果为：

$$
    \begin{bmatrix}
        d4 & e0 & b8 & 1e \\
        27 & bf & b4 & 41 \\
        11 & 98 & 5d & 52 \\
        ae & f1 & e5 & 30
    \end{bmatrix}
$$

\vspace{0.5cm}

\subsection{行移位（ShiftRows）}

行移位需要将矩阵的每一行循环左移相应的位数，其中第一行不需要移位，第二行需要左移一位，第三行需要左移两位，第四行需要左移三位。\\

对上一步经过字节代换后的矩阵进行行移位后的结果为：

$$
    \begin{bmatrix}
        d4 & e0 & b8 & 1e \\
        bf & b4 & 41 & 27 \\
        5d & 52 & 11 & 98 \\
        30 & ae & f1 & e5
    \end{bmatrix}
$$

\vspace{0.5cm}

\subsection{列混合（MixColumns）}

在列混合过程中，需要使用一个给定的$ 4 \times 4 $矩阵，乘上上一步行移位后的矩阵。

$$
    \begin{bmatrix}
        02 & 03 & 01 & 01 \\
        01 & 02 & 03 & 01 \\
        01 & 01 & 02 & 03 \\
        03 & 01 & 01 & 02
    \end{bmatrix}
    \times
    \begin{bmatrix}
        d4 & e0 & b8 & 1e \\
        bf & b4 & 41 & 27 \\
        5d & 52 & 11 & 98 \\
        30 & ae & f1 & e5
    \end{bmatrix}
$$

\vspace{0.5cm}

但是这里使用的乘法不是普通的矩阵乘法，而是使用了有限域$ GF(2^8) $上的乘法。\\

例如对于矩阵第1行第1列的计算：

\vspace{-1cm}

\begin{align*}
    S_{00} & = 02 \times d4 + 03 \times bf + 01 \times 5d + 01 \times 30 \\
           & = 02 \times d4 + 03 \times bf + 5d + 30
\end{align*}

其中加法的运算需要使用异或：

\vspace{-1cm}

\begin{align*}
    S_{00} = 02 \times d4 \oplus 03 \times bf \oplus 5d \oplus 30
\end{align*}

而乘法的运算，需要使用给定的规则：

\begin{enumerate}
    \item \begin{equation*}
              (00000010) \times (a_7a_6a_5a_4a_3a_2a_1a_0) =
              \begin{cases}
                  (a_6a_5a_4a_3a_2a_1a_00)                   & \text{$ a_7 = 0 $} \\
                  (a_6a_5a_4a_3a_2a_1a_00) \oplus (00011011) & \text{$ a_7 = 1 $}
              \end{cases}
          \end{equation*}

    \item \begin{align*}
               & (00000011) \times (a_7a_6a_5a_4a_3a_2a_1a_0)                                                  \\
               & = \left[(00000010) \times (a_7a_6a_5a_4a_3a_2a_1a_0)\right] \oplus (a_7a_6a_5a_4a_3a_2a_1a_0)
          \end{align*}
\end{enumerate}

其中第二条规则中的乘法运算，需要再次使用第一条规则的方式计算。

\vspace{-1cm}

\begin{align*}
    02 \times d4 & = (00000010) \times (11010100)                                \\
                 & = (10101000) \oplus (00011011)                                \\
                 & = 10110011                                                    \\
    \\
    03 \times bf & = (00000011) \times (10111111)                                \\
                 & = \left[(00000010) \times (10111111)\right] \oplus (10111111) \\
                 & = \left[(01111110) \oplus (00011011)\right] \oplus (10111111) \\
                 & = 110110101
\end{align*}

\vspace{-1cm}

\begin{align*}
    S_{00} & = 02 \times d4 \oplus 03 \times bf \oplus 5d \oplus 30               \\
           & = (10110011) \oplus (110110101) \oplus (01011101)  \oplus (00110000) \\
           & = 00000100                                                           \\
           & = 04
\end{align*}

\vspace{0.5cm}

\subsection{轮密钥加（AddRoundKey）}

在经过列混合后，将得到的结果矩阵与该轮的密钥矩阵进行异或运算，得到的结果即为该轮的输出。

$$
    \begin{bmatrix}
        04 & e0 & 48 & 28 \\
        66 & cb & f8 & 06 \\
        81 & 19 & d3 & 26 \\
        e5 & 9a & 7a & 4c
    \end{bmatrix}
    \oplus
    \begin{bmatrix}
        a0 & 88 & 23 & 2a \\
        fa & 54 & a3 & 6c \\
        fe & 2c & 39 & 76 \\
        17 & b1 & 39 & 05
    \end{bmatrix}
    =
    \begin{bmatrix}
        a4 & 68 & 6b & 02 \\
        9c & 9f & 5b & 6a \\
        7f & 35 & ea & 50 \\
        f2 & 2b & 43 & 49
    \end{bmatrix}
$$

\newpage